package com.cqs.leetcode.array;

import java.util.ArrayList;
import java.util.List;

/**
 * lixw
 * 2021/11/1
 **/
public class FindMinimumRotatedSortedArray153 {
    //1. 所有的数不同
    //2, 要么整体是单调递增的 要么最低点为分割 两段是单调的
    public int findMin(int[] nums) {
        //2分法求最小值
        int left = 0, right = nums.length - 1;
        while (left < right) {
            //整体是单调的 [1,2] 直接返回
            if (nums[left] < nums[right]){
                return nums[left];
            }
            int mid = (left + right) / 2;
            //左侧单调递增 在右边【含mid】
            //注意这里有等于 [7,1]
            if (nums[left] <= nums[mid]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left];
    }

    public static void main(String[] args) {
        FindMinimumRotatedSortedArray153 f = new FindMinimumRotatedSortedArray153();
        List<int[]> cases = new ArrayList<>();
        cases.add(new int[]{7,1});
        cases.add(new int[]{4,5,6,7,1,2,3});
        cases.add(new int[]{3,4,5,6,7,1,2});
        cases.add(new int[]{5,6,7,1,2,3,4});
        for (int[] c:cases) {
            System.out.println(f.findMin(c));
        }
    }
}
